---
title: "哞叫时间2"
created: 2025-11-28
tags:
  - 算法
---

# 哞叫时间2

## 题目 [哞叫时间2](https://www.acwing.com/problem/content/description/6137/)

![[a40328cac658be7798c6e9c115074613-a40328ca.png]]

## 思路分析

每输入一个数 就记录该数出现的次数

如果达到两次 就说明BB形成

所有在第一个B前面的A都可以组成一种方案

用哈希表可以计数 一旦找到直接+=size即可

问题是怎么找到第一个B

按一般思维来看 在遍历找A的时候 如果遇到了B就应该立即停止吧

因为BB必须是在A之前 一旦找到了第一个B 还继续的话 就可能形成BAB 而不是ABB

但是如果立即停止的话 是否又会形成这种 ABBABAB 遗漏掉第二个A与最后两个B组成的ABB情况

该怎么处理

可以倒着找BB 记录每个B出现的位置 尤其重要的是B第二次出现的位置 逆着第二次出现也就是正着第一次出现 即我们要的第一个B的位置

如果B出现多次呢（超过两次） 没关系 ABCBDBB 只考虑最后两个B（把倒数第二个B作为第一个B 也能包含ABB CBB DBB 所有以BB为后缀结尾的情况）

记录到了ABB中B的第一次出现位置 就可以直接正着循环按上面的思路走了

## 代码实现

```cpp
#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long ll;

typedef pair<int, int> PII;

const int N = 1e6 + 9;

int a[N];

unordered_map<int, PII> local;  // 记录每个数字第一次和第二次出现的位置

unordered_map<int, int> cnt;  // 记录每个数字在遍历过程中已经出现的次数

int main() {

    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n;cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];

    ll ans = 0;

    // 从后往前遍历，记录每个数字的第一次和第二次出现位置

    for (int i = n; i >= 1; i--) {

        if (!local[a[i]].first)

            local[a[i]].first = i;

        else {

            if (!local[a[i]].second)

                local[a[i]].second = i;

        }

    }

    // 从前往后遍历，计算合法的 ABB 子序列

    for (int i = 1; i <= n; i++) {

        // 如果当前数字的当前位置是它的第二次出现位置，且第一次出现已经记录过(ABB中的第一个B的位置 前面的所有数都可以作为A组成ABB)

        if (i == local[a[i]].second && local[a[i]].first) {

            ans += cnt.size();

            if (cnt[a[i]])

                ans--;  //自己不算 否则成BBB

        }

        cnt[a[i]]++;

    }

    cout << ans;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[哞叫时间|哞叫时间]] 🏠 [[00-刷题理模型]] ➡️ [[奶牛体操|奶牛体操]]